package com.kongge.algorithm.tree;

import java.util.LinkedList;
import java.util.List;

public class BinarySearchTree<T extends Comparable> implements ITree<T> {
	TreeNode<T> rootNode;
	private int size;

	public BinarySearchTree() {
		size = 0;
	}
	public void add(T t) {
		if (t == null) {
			return;
		}
		if (rootNode == null) {
			rootNode = new TreeNode<T>(t);
			size ++;
		} else {
			if (addInner(rootNode, t)) {
				size ++;
			}
		}
	}
	
	public boolean remove(T t) {
		return false;
	}
	
	public int size() {
		return size;
	}
	
	private boolean addInner(TreeNode<T> root, T t) {
		int result = t.compareTo(root.value);
		if (result == 0) {
			return false;
		}
		if (result < 0 && root.left == null) {
			root.left = new TreeNode<T>(t);
			return true;
		}
		if (result > 0 && root.right == null) {
			root.right = new TreeNode<T>(t);
			return true;
		}
		return addInner(result < 0 ? root.left : root.right, t);
	}
	
	/**
	 * 
	 * @param type
	 * @return
	 */
	public List<T> traveseTreeByType(int type) {
		if (rootNode == null) {
			return null;
		}
		List<TreeNode<T>> resultList = new LinkedList<TreeNode<T>>();
		switch (type) {
		case ITree.TRAVESE_TYPE_PRE:
			TreeNode.preTraveseTree(rootNode, resultList);
			break;
		case ITree.TRAVESE_TYPE_MID:
			TreeNode.middleTraveseTree(rootNode, resultList);
			break;
		case ITree.TRAVESE_TYPE_SUFF:
			TreeNode.suffTraveseTree(rootNode, resultList);
			break;
		case ITree.TRAVESE_TYPE_ARRANGE:
		default:
			TreeNode.arrangementTraveseTree(rootNode, resultList);
			break;
		}
		
		List<T> result = new LinkedList<T>();
		for (int i = 0; i < resultList.size(); i++) {
			result.add(resultList.get(i).value);
		}
		return result;
	}
}
